Codeforces Round 538 (Div. 2)

Diposting di | Edited on

传送门

A.Got Any Grapes? (水题)

手冷把y写成x被fst了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int x,y,z,a,b,c;
    cin>>x>>y>>z;
    cin>>a>>b>>c;
    if(a<x){
        cout<<"NO"<<endl;exit(0);
    }
    a-=x;
    b=a+b;
    if(b<y){
        cout<<"NO"<<endl;return 0;
    }
    b-=y;
    c+=b;
    if(c<z){
        cout<<"NO"<<endl;return 0;
    }
    cout<<"YES"<<endl;
    return 0;
}

B.Yet Another Array Partitioning Task (毒瘤？)

题意

让你分出k个区间，每个区间至少m个数，然后取每个区间的前m个最大值相加，使值最大

思路

本质就是求前m*k大的数,然后我们就可以把前m×k大的数求出来 然后记录坐标，然后连续m个分为一组即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
struct node{
    ll value;
    int id;
    bool operator<(const node &a)const{
        return value>a.value;
    }
}my[maxn];
bool f[maxn];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n;
    ll m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)cin>>my[i].value,my[i].id=i;
    sort(my+1,my+1+n);
    ll ans=0;
    for(ll i=1;i<=m*k;i++){
        ans+=my[i].value;f[my[i].id]=1;
    }
    cout<<ans<<endl;
    for(int i=1,t=0,p=0;i<=n;i++){
        if(f[i]){
            t++;
            if(t==m){
                cout<<i<<" ";t=0;
                p++;
                if(p==k-1)return 0;
            }
        }
    }
    return 0;
}

C. Trailing Loves (or L’oeufs?) (质因子分解)

题意

求n!在b进制下末尾0的个数

思路

只要会十进制下求n！的就会这题了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
ll prime[maxn][2];
int tot;
ll hello(ll n,ll p){
    ll ans=0;
    while(n){
        ans+=n/p;
        n/=p;
    }
    return ans;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    ll n,m;
    cin>>n>>m;
    for(ll i=2;i<=sqrt(m);i++){
        if(m%i==0){
            prime[++tot][0]=i;
            while(m%i==0){
                m/=i;
                prime[tot][1]++;
            }
        }
    }
    if(m!=1){
        prime[++tot][0]=m;prime[tot][1]=1;
    }
    ll ans=inf;
    for(int i=1;i<=tot;i++){
            ans=min(ans,hello(n,prime[i][0])/prime[i][1]);
    }
    cout<<ans<<endl;
    return 0;
}

D.Flood Fill (区间DP，本质求LCS，记忆化搜索)

题意

一个颜色序列，每个位置有一个颜色，选择一个起始位置，每次可以改变左右的一段颜色段（如果左边和右边颜色一样就一起改变），把整段变成一种颜色， 问最少操作多少次。n<=5000

思路

首先一整段颜色段肯定没用,我们可以缩点，简化题意

然后想到区间DP（石子合并） 但是石子合并是可以任意起点，而这题固定起点了，

所以可以把区间DP的n^3变成n^2了，我区间DP很差所以比赛只想出来记忆化搜索

记忆化搜索对付这种只有终点没有起点的题真的是屡试不爽

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int c[maxn];
int a[maxn];
int dp[5500][5500];
int dfs(int l,int r){
    if(dp[l][r]!=-1)return dp[l][r];
    int ans=0;
    if(l==r)return 0;
    if(a[l]==a[r])ans=dfs(l+1,r-1)+1;
    else ans=min(dfs(l+1,r),dfs(l,r-1))+1;
    dp[l][r]=ans;
    return ans;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>c[i];
    }
    a[1]=c[1];int cnt=1;
    for(int i=2;i<=n;i++){
        if(a[cnt]!=c[i]){
            a[++cnt]=c[i];
        }
    }
  /*  for(int i=1;i<=cnt;i++){
        cout<<a[i]<<" ";
    }*/
    memset(dp,-1,sizeof(dp));
    cout<<dfs(1,cnt)<<endl;
    return 0;
}

E.Arithmetic Progression (mt19937+交互题+二分找最大值+随机数取GCD)

题意

你电脑中有一个等差数列,你有两种循环

1.问这个数列的第x项的值

2.问是否有一个项的值比X大

让你在60次内找出这个等差数列的首项和公差

思路

很明显可以在32次内得出最大值，然后就是求公差了，

我们既然有了最大值，那我们就可以求出任意一项和最大值的差值肯定是公差的倍数

然后我们就直接对这些差值求GCD

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int n,k,m,ti=60;
mt19937_64 lwt(time(0));
int ask(int x){
    cout<<"? "<<x<<endl;
    cin>>k;
    return k;
}
int ask2(int x){
    cout<<"> "<<x<<endl;
    cin>>k;
    ti--;
    return k;
}
int find_max(){
    int l=-1,r=1e9;
    int ans;
    while(r-l>=0){
        int mid=(l+r)/2;
        if(ask2(mid))l=mid+1;else r=mid-1,ans=mid;
    }
    return ans;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    cin>>n;
    m=find_max();
    int d=0;
    for(int i=1;i<=ti;i++){
        int id=lwt()%n+1;
        int x=ask(id);
        if(x!=m)d=__gcd(d,m-x);
    }
    cout<<"! "<<m-(n-1)*d<<" "<<d<<endl;
    return 0;
}

F.Please, another Queries on Array? (线段树区间乘+欧拉函数+bitset)

题意

两个操作

1.把一个区间乘上一个值X

2.求一个区间的欧拉函数

思路

看到区间乘法很容易想到线段树

那么欧拉函数怎么求，很明显欧拉函数和素因子个数有关

发现每个x都小于等于300 打表发现300内的素因子只有62个

然后就是怎么记录这几个素因子的问题了，你可以用LL的位数或者bitset记录

（或者用数组？那可能会超时吧）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=4e5+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int n,q;
bool isprime[500];
ll prime[500];
ll inv[500];
ll Pow(ll a,ll i){
    ll s=1LL;
    while(i){
        if(i&1)s=1LL*s*a%mod;
        a=1LL*a*a%mod;
        i>>=1;
    }
    return s;
}
int init(int n){
    int p=0;
    for(int i=0;i<=n;i++)isprime[i]=true;
    isprime[0]=isprime[1]=false;
    for(int i=2;i<=n;i++){
        if(isprime[i])prime[p++]=i*1LL;
        for(int j=0;j<p;j++){
            if(prime[j]*i>n)break;
            isprime[prime[j]*i]=false;
            if(i%prime[j]==0)break;
        }
    }
    return p;
}
ll a[maxn];
struct segtree{
    bitset<62>has[maxn<<2];
    bitset<62>laz[maxn<<2];
    ll ans[maxn<<2];
    ll lazy[maxn<<2];
    void pushup(int o){
        ans[o]=1LL*ans[o<<1]*ans[o<<1|1]%mod;
        has[o]=has[o<<1]|has[o<<1|1];
    }
    void pushdown1(int o,int l,int r){
        if(lazy[o]==1)return;
        int mid=(l+r)/2,len1=mid-l+1,len2=r-mid;
        lazy[o<<1]=1LL*lazy[o<<1]*lazy[o]%mod;
        ans[o<<1]=1LL*ans[o<<1]*Pow(lazy[o],len1)%mod;
        lazy[o<<1|1]=1LL*lazy[o<<1|1]*lazy[o]%mod;
        ans[o<<1|1]=1LL*ans[o<<1|1]*Pow(lazy[o],len2)%mod;
        lazy[o]=1;
    }
    void pushdown2(int o){
        laz[o<<1]|=laz[o];
        has[o<<1]|=laz[o];
        laz[o<<1|1]|=laz[o];
        has[o<<1|1]|=laz[o];
        laz[o].reset();
    }
    void build(int o,int l,int r){
        lazy[o]=1;has[o].reset();laz[o].reset();
        if(l==r){
            ans[o]=a[l];
            for(int i=0;i<62;i++)if(a[l]%prime[i]==0)has[o].set(i);
            return;
        }
        int mid=(l+r)/2;
        build(o<<1,l,mid);build(o<<1|1,mid+1,r);
        pushup(o);
    }
    void update(int o,int l,int r,int ql,int qr,ll v,bitset<62> bit){
        if(ql<=l&&r<=qr){
            lazy[o]=1LL*lazy[o]*v%mod;
            ans[o]=1LL*ans[o]*Pow(v,r-l+1)%mod;
            laz[o]|=bit;has[o]|=bit;
            return;
        }
        pushdown1(o,l,r);
        pushdown2(o);
        int mid=(l+r)/2;
        if(ql<=mid)update(o<<1,l,mid,ql,qr,v,bit);
        if(qr>mid)update(o<<1|1,mid+1,r,ql,qr,v,bit);
        pushup(o);
    }
    ll query1(int o,int l,int r,int ql,int qr){
        if(ql<=l&&r<=qr)return ans[o];
        pushdown1(o,l,r);
        int mid=(l+r)/2;
        ll ans=1;
        if(ql<=mid)ans=ans*query1(o<<1,l,mid,ql,qr)%mod;
        if(qr>mid)ans=ans*query1(o<<1|1,mid+1,r,ql,qr)%mod;
        return ans;
    }
    bitset<62> query2(int o,int l,int r,int ql,int qr){
        if(ql<=l&&r<=qr)return has[o];
        pushdown2(o);
        int mid=(l+r)/2;
        bitset<62> ans;ans.reset();
        if(ql<=mid)ans|=query2(o<<1,l,mid,ql,qr);
        if(qr>mid)ans|=query2(o<<1|1,mid+1,r,ql,qr);
        return ans;
    }

}seg;
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int p=init(300);
    for(int i=0;i<p;i++)inv[i]=Pow(1LL*prime[i],mod-2);
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    seg.build(1,1,n);
    while(q--){
        int l,r;
        ll x;char str[10];
        cin>>str;
        if(str[0]=='T'){
            cin>>l>>r;
            ll res=seg.query1(1,1,n,l,r);
            bitset<62> bit=seg.query2(1,1,n,l,r);
            for(int j=0;j<62;j++)
                if(bit[j])res=(1LL*res*inv[j]%mod*(prime[j]-1+mod)%mod)%mod;
            cout<<res<<endl;
        }
        else{
            cin>>l>>r>>x;
            bitset<62>bit;bit.reset();
            for(int j=0;j<62;j++)if(x%prime[j]==0)bit.set(j);
            seg.update(1,1,n,l,r,x,bit);
        }
    }
    return 0;
}